package com.njupt.DoublePoint;


import threshold.ListNode;

/**
 * 206. 反转链表
 */
public class ReverseList {


    /**
     * 前插法
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        ListNode list = new ListNode();
        ListNode p = head;
        while(p != null){

            ListNode node = new ListNode(p.val);
            node.next = list.next;
            list.next = node;
            p = p.next;
        }


        return list.next;
    }

    /**
     * 双指针法
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head){

        ListNode pre = null;
        ListNode rear = head;
        ListNode next = null;

        while(rear != null){
            next = rear.next;
            rear.next = pre;
            pre = rear;
            rear = next;

        }
        return pre;
    }

    /**
     * 反转链表递归法
     * @param head
     * @return
     */
    public ListNode reverseListRecur(ListNode head){
        return reverseCur(null,head);

    }

    /**
     * 归结束的条件:rear指针为空
     * 递归链条:反转前后两个节点
     * 个人理解：其实可以吧递归看成是 while循环的一种方式
     * @param pre
     * @param rear
     * @return
     */
    public ListNode reverseCur(ListNode pre,ListNode rear){
        if(rear == null){
            return pre;
        }
        ListNode next = rear.next;
        rear.next = pre;
//        pre = rear;
//        rear = next;
        return reverseCur(rear,next);
    }
    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ReverseList test = new ReverseList();
        ListNode listNode = test.reverseListRecur(node1);

        ListNode p = listNode;
        while(p != null){

            System.out.print(p.val + " ");
            p = p.next;
        }


    }
}


